#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-22 10:32 上午
# @Author  : yangdy
# @File    : 2020-09-22.968.监控二叉树
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        self.ans = 0

        def dfs(rt):
            if not rt:
                return 2
            left = dfs(rt.left)
            right = dfs(rt.right)
            if left == 0 or right == 0:
                self.ans += 1
                return 1
            elif left == 1 or right == 1:
                return 2
            else:
                return 0

        self.ans = self.ans + 1 if dfs(root) == 0 else self.ans
        return self.ans


questions = [
    ([0, 0, None, 0, 0],),
    ([0, 0, None, 0, None, 0, None, None, 0],),
]


work(questions, lambda q: Solution().minCameraCover(mk_tree(q[0], TreeNode)))
